package leetcode.code0188;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：110 ms, 在所有 Java 提交中击败了6.44%的用户
 *
 * 内存消耗：38.3 MB, 在所有 Java 提交中击败了28.11%的用户
 *
 * 通过测试用例：211 / 211
 */
public class Solution2 implements IDebug {

	public int maxProfit(int k, int[] prices) {
		int len = prices.length;
		if (k == 0 || len < 2)
			return 0;
		k = Math.min(k, len >> 1);
		int[][] dp = new int[len + 1][k + 1];// d[i][j]截至第i天做了j次交易，最大收入是多少
		for (int i = 2; i <= len; i++) {
			int cur = prices[i - 1];
			for (int j = 1; j <= k; j++) {
				int max = dp[i - 1][j];
				for (int m = 1; m < i; m++) {
					int last = prices[m - 1];
					max = Math.max(cur - last + dp[m - 1][j - 1], max);
				}
				dp[i][j] = max;
			}
		}
//		int ans = 0;
//		H.printObject(dp);
//		for (int j = 0; j <= k; j++) {
//			ans = Math.max(dp[len][j], ans);
//		}
		return dp[len][k];
	}

	@Override
	public void debug1() {
		HelpDebug.compare(2, this.maxProfit(2, HelpDebug.str2array3("[2,4,1]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(8, this.maxProfit(1, HelpDebug.str2array3("[3,2,6,5,3,10]")));

		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		HelpDebug.compare(11, this.maxProfit(2, HelpDebug.str2array3("[3,2,6,5,3,10]")));

		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
